import java.util.Stack;

public class Preorder {
    public static void preOrderTravel(TreeNode root){
        if (root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || stack != null){
            while(cur != null){
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode tmp = stack.pop();
            cur = tmp.right;

        }
    }
    public static void main(String[] args) {
        TreeNode root =  new TreeNode(1,null,null);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        preOrderTravel(root);
    }
}
